package com.demo.app.sort;


import java.util.Arrays;

/**
 * @program: couple-game
 * @description: 排序
 * @author: fbl
 * @create: 2025-04-23 09:26
 **/
public class Sort {

    public static void main(String[] args) {
        int[] arr = {1, 5, 3, 2, 4};
//        chooseSort(arr);
//        bubblingSort(arr);
        insertSort(arr);
    }


    /**
     * 选择排序
     *
     * @param arr
     */
    public static void chooseSort(int[] arr) {
        int N = arr.length;

        for (int i = 0; i < N; i++) {
            int minIndex = i;
            for (int j = i + 1; j < N; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            // 交换
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubblingSort(int[] arr) {
        int N = arr.length;

        for (int end = N - 1; end > 0; end--) {
            for (int j = 1; j <= end; j++) {
                if (arr[j - 1] > arr[j]) {
                    // 前一个数比后一个数大 交换
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 插入排序
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {
        int N = arr.length;
        // 0 ~ 0 完成 0~1 0~2 0~3 0 ~ n-1 区间
        for (int i = 1; i < N; i++) {
//            int newIndex = i;
//            while((newIndex -1 >= 0) && arr[newIndex - 1] > arr[newIndex]){
//                // 交换
//                int temp = arr[newIndex];
//                arr[newIndex] = arr[newIndex - 1];
//                arr[newIndex - 1] = temp;
//                newIndex--;
//            }
            for(int newIndex = i;(newIndex -1 >= 0) && arr[newIndex - 1] > arr[newIndex];newIndex--){
                // 交换
                int temp = arr[newIndex];
                arr[newIndex] = arr[newIndex - 1];
                arr[newIndex - 1] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));

    }
}
